package cn.chen.算法.排序;

import java.util.Arrays;

/**
 * 堆排序：堆就是满足条件的完全二叉树：
 *  条件：
 *      节点大于或等于左右孩子结点。
 *      节点小于或等于左右孩子结点。
 *
 */
public class HeapSort {

    public static void main(String[] args) {

        int[] a={4,6,8,5,9};
        heapSort(a);
        System.out.println(Arrays.toString(a));

    }

    // 堆排序的方法
    public static void heapSort(int[] a) {

        int temp=0;

        // 将数据调整成大顶堆
        for(int i=a.length/2-1;i>=0;i--){

            adjustHeap(a,i,a.length);
        }

        // 交换
        for(int j=a.length-1;j>0;j--){

            temp=a[j];
            a[j]=a[0];
            a[0]=temp;

            // 继续找出从0到length-1索引的大顶堆
            adjustHeap(a,0,j);
        }
    }
    // 将一个数组（二叉树）调整为一个大顶堆
    /**
     * 功能：完成将 以i为父节点的树（局部）变为大顶堆
     *
     * @param a      待调整的数组
     * @param i      表示非叶子结点在数组中的索引
     * @param length 表示对多少个元素进行调整，length是在逐渐减少
     */
    public static void adjustHeap(int[] a, int i, int length) {

        int temp = a[i];  // 取出当前元素的值，保存在临时变量中

        // 开始调整
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {  // 初始k为i的左子节点，每次循环k都指向k的左子节点

            if(k+1<length&&a[k]<a[k+1]) // 比较左子节点小于右子节点
                k++;    // 将k指向右子节点

            if(a[k]>temp){

                a[i]=a[k];  // 将较大的值赋值给当前节点
                i=k;    // i 指向k， 继续循环比较
            }
            else break;     // 跳出循环
        }
        // 当for循环结束之后，我们已经将以i为父节点的树（局部）中的最大值，放在了最顶端。
        a[i]=temp;  // 将temp放到调整后的位置
    }
}